Computer networks are an established part of everyday life. Most medium to large businesses, and even many small businesses, have some form of network established within the office and which connects with other networks in other offices, for example, via the Internet. Further, it is becoming more and more common for homeowners to establish networks within their residence to interconnect multiple computer stations and to connect to the Internet.
Generally, a typical network connection comprises a path between a source (e.g., a PC configured with a software client) and a destination (e.g., a network server), referred to herein as a “source-destination pair”. There are typically multiple potential paths between the source and destination, with the optimal path for a connection between a particular source-destination pair referred to herein as the “primary path” or the “primary LSP”. Alternate routes between the same source-destination pair, which may be many, are referred to herein as “backup paths” or “protection LSPs”.
Restoration of network connections, and the ability to create “self-healing” network connections, are a major and growing concern for today's network and network administrators. Restoration is the ability of a network to re-route traffic from one path (typically the primary path) between a source-destination pair, to another path (a backup path) between the same source-destination pair. These reroutes are desirable in the event of a failure. The new path to which traffic is switched is called the restored or back-up path, and may be precomputed (i.e., determined by pre-analysis of the possible network connections and a predetermination of backup paths to be used if needed) or dynamically computed (calculated “on the fly” based on an instantaneous analysis of the available paths at the time of the failure).
There are several known types of restoration schemes, each of which has pros and cons. Two of the more common restoration schemes are the dedicated mesh (1+1) protection and the shared mesh (1:N) restoration schemes. Dedicated mesh protection provides fast recovery, since there is a dedicated backup path allocated for each primary path. In the event of a failure, the failed portion of the primary path is simply switched out of the network connection in favor of the dedicated secondary path provided for that link of the primary path.
Shared mesh restoration allocates a single restoration path that is shared among multiple (N) network links. Compared to dedicated mesh protection, shared mesh restoration allows considerable saving in terms of the capacity required to provide the protection. In addition, the backup resources can be utilized for lower priority preemptable traffic in normal network operating mode, that is, the backup paths may be used to carry live revenue generating traffic, with the understanding that such traffic may be bumped off if there is a failure somewhere in the network, and that particular path is needed for restoration. In view of the ability to utilize a single path to provide protection for multiple network links, the use of shared mesh restoration has become the preferred method where low cost and/or reduced component size is an issue.
In a shared mesh restoration scheme (1:N) there are N primary paths that share one path for their backup. For example, a set of links in the network can act as a backup route for N different primary paths, even where the N different primary paths do not correspond to the same source-destination pair. From the perspective of individual links L (also referred to as “segments”) in a backup path, each link ‘L’ is only “aware” of the primary paths for which it provides protection, and has no awareness of the primary paths for which other links similar to ‘L’ within the same backup path provide protection.
Primary paths and backup paths typically comprise multiple links connecting the multiple nodes in the primary or backup path. Links in the primary path are referred to herein as “primary links” and links in the backup path are referred to herein as “backup links.” When multiple parallel primary paths (i.e., primary paths with no common links) share a single backup path, the backup path need only reserve as much bandwidth as that required by the primary path carrying the largest bandwidth. However, since the paths (primary or backup) are made up of multiple links, this bandwidth determination is made on a link-by-link basis. The backup bandwidth necessary to be reserved for a particular backup link L, given by ‘BL’ is given by Equation (1):BL=MAX (ΣKji=1Fi,j)j=1j=N                where, Fi,j=bandwidth of path i, on primary link j, KJ=number of paths on link j        
Each link L “belongs” to a certain node in the network for the purpose of scheduling traffic, that is, scheduling is performed based on the outgoing interface of a link, and there is only one outgoing interface with respect to one node and a given link. Thus, for each node, the various Kj's (number of paths K on a particular primary link j) must be computed for each link L belonging to that node. The prior art approach for performing this computation has been to use extensions to OSPF/OSPF-TE. By using opaque LSAs (Link State Advertisements), each node transmits and maintains information about the number of primary links in the network whose backup path constitutes a link L in the network. In other words, every transmitting node T in the network transmits/floods opaque LSAs to every other node, so as to provide information about all primary paths across all of its interfaces. A receiving node R, in order to perform the backup bandwidth computation, goes through the entire LSA database to search for all relevant primary paths that affect the computation for a local link L.
The methodology described above is cumbersome because it requires that several messages be sent through the network to identify and obtain the various backup path possibilities. Moreover, the information might not always be fresh, since in OSPF, messages/LSAs have only a certain finite refresh frequency. When a particular path is calculated by a general protocol, in this case OSPF, the reservation procedures try to reserve the required amount of bandwidth. However, if the information distributed by OSPF is stale, an “undo” procedure is required. This undo procedure is called a crankback. With OSPF, only after the reservation is made is it possible to know for sure the actual amount of bandwidth that is required, and hence that a crankback might be needed, because the reservation may have taken more than the calculated bandwidth, and hence a new backup path would be tried that is equal or closer to the calculated bandwidth.
Further, the sharing information database must be replicated (as part of the LSA database), even if all of the nodes do not require the entire database (only those primary links which affect a particular backup link ‘L’ are needed for the calculation, i.e., a node only needs the information about the primary links across all of its interfaces/links, and not all the links in the network). This is because OSPF is a distributed or “flooding” protocol, and thus distributes all of the information about all links in the network, whether they are needed or not. This is overkill in both resources (e.g., memory), and CPU usage. In addition to increasing the memory overhead, using OSPF also increases the computation overhead, since the search through the database is comprehensive. In other words, to solve equation (1), OSPF determines KJ's for all J's, and Fi,j for every i and every j, for each and every node. Much of this computation is unnecessary for the goal of identifying the optimal backup paths; however, using OSPF, it cannot be avoided.
Accordingly, it would be desirable to have a technique for calculating the optimal backup path(s) for a network whereby the data used to perform the calculation is always fresh; where every node in the network maintains only as much information as is needed to make the calculation; and where a minimum number of nodes are used in synchronizing the distributed database.